QUnit.module('depthFirstSearch', () =>
{
    QUnit.test('should perform DFS operation on graph', (assert) =>
    {
        const graph = new ds.Graph(true);

        const vertexA = new ds.GraphVertex('A');
        const vertexB = new ds.GraphVertex('B');
        const vertexC = new ds.GraphVertex('C');
        const vertexD = new ds.GraphVertex('D');
        const vertexE = new ds.GraphVertex('E');
        const vertexF = new ds.GraphVertex('F');
        const vertexG = new ds.GraphVertex('G');

        const edgeAB = new ds.GraphEdge(vertexA, vertexB);
        const edgeBC = new ds.GraphEdge(vertexB, vertexC);
        const edgeCG = new ds.GraphEdge(vertexC, vertexG);
        const edgeAD = new ds.GraphEdge(vertexA, vertexD);
        const edgeAE = new ds.GraphEdge(vertexA, vertexE);
        const edgeEF = new ds.GraphEdge(vertexE, vertexF);
        const edgeFD = new ds.GraphEdge(vertexF, vertexD);
        const edgeDG = new ds.GraphEdge(vertexD, vertexG);

        graph
            .addEdge(edgeAB)
            .addEdge(edgeBC)
            .addEdge(edgeCG)
            .addEdge(edgeAD)
            .addEdge(edgeAE)
            .addEdge(edgeEF)
            .addEdge(edgeFD)
            .addEdge(edgeDG);

        assert.deepEqual(graph.toString(), 'A,B,C,G,D,E,F');

        var enterVertexCallbackCalls = [];
        var leaveVertexCallbackCalls = [];
        const enterVertexCallback = ({ previousVertex, currentVertex }) => enterVertexCallbackCalls.push({ previousVertex, currentVertex });
        const leaveVertexCallback = ({ previousVertex, currentVertex }) => leaveVertexCallbackCalls.push({ previousVertex, currentVertex });

        // Traverse graphs without callbacks first to check default ones.
        ds.depthFirstSearch(graph, vertexA);

        // Traverse graph with enterVertex and leaveVertex callbacks.
        ds.depthFirstSearch(graph, vertexA, {
            enterVertex: enterVertexCallback,
            leaveVertex: leaveVertexCallback,
        });

        assert.deepEqual(enterVertexCallbackCalls.length, graph.getAllVertices().length);
        assert.deepEqual(leaveVertexCallbackCalls.length, graph.getAllVertices().length);

        const enterVertexParamsMap = [
            { currentVertex: vertexA, previousVertex: null },
            { currentVertex: vertexB, previousVertex: vertexA },
            { currentVertex: vertexC, previousVertex: vertexB },
            { currentVertex: vertexG, previousVertex: vertexC },
            { currentVertex: vertexD, previousVertex: vertexA },
            { currentVertex: vertexE, previousVertex: vertexA },
            { currentVertex: vertexF, previousVertex: vertexE },
        ];

        for (let callIndex = 0; callIndex < graph.getAllVertices().length; callIndex += 1)
        {
            const params = enterVertexCallbackCalls[callIndex];
            assert.deepEqual(params.currentVertex, enterVertexParamsMap[callIndex].currentVertex);
            assert.deepEqual(params.previousVertex, enterVertexParamsMap[callIndex].previousVertex);
        }

        const leaveVertexParamsMap = [
            { currentVertex: vertexG, previousVertex: vertexC },
            { currentVertex: vertexC, previousVertex: vertexB },
            { currentVertex: vertexB, previousVertex: vertexA },
            { currentVertex: vertexD, previousVertex: vertexA },
            { currentVertex: vertexF, previousVertex: vertexE },
            { currentVertex: vertexE, previousVertex: vertexA },
            { currentVertex: vertexA, previousVertex: null },
        ];

        for (let callIndex = 0; callIndex < graph.getAllVertices().length; callIndex += 1)
        {
            const params = leaveVertexCallbackCalls[callIndex];
            assert.deepEqual(params.currentVertex, leaveVertexParamsMap[callIndex].currentVertex);
            assert.deepEqual(params.previousVertex, leaveVertexParamsMap[callIndex].previousVertex);
        }
    });

    QUnit.test('allow users to redefine vertex visiting logic', (assert) =>
    {
        const graph = new ds.Graph(true);

        const vertexA = new ds.GraphVertex('A');
        const vertexB = new ds.GraphVertex('B');
        const vertexC = new ds.GraphVertex('C');
        const vertexD = new ds.GraphVertex('D');
        const vertexE = new ds.GraphVertex('E');
        const vertexF = new ds.GraphVertex('F');
        const vertexG = new ds.GraphVertex('G');

        const edgeAB = new ds.GraphEdge(vertexA, vertexB);
        const edgeBC = new ds.GraphEdge(vertexB, vertexC);
        const edgeCG = new ds.GraphEdge(vertexC, vertexG);
        const edgeAD = new ds.GraphEdge(vertexA, vertexD);
        const edgeAE = new ds.GraphEdge(vertexA, vertexE);
        const edgeEF = new ds.GraphEdge(vertexE, vertexF);
        const edgeFD = new ds.GraphEdge(vertexF, vertexD);
        const edgeDG = new ds.GraphEdge(vertexD, vertexG);

        graph
            .addEdge(edgeAB)
            .addEdge(edgeBC)
            .addEdge(edgeCG)
            .addEdge(edgeAD)
            .addEdge(edgeAE)
            .addEdge(edgeEF)
            .addEdge(edgeFD)
            .addEdge(edgeDG);

        assert.deepEqual(graph.toString(), 'A,B,C,G,D,E,F');

        var enterVertexCallbackCalls = [];
        var leaveVertexCallbackCalls = [];
        const enterVertexCallback = ({ previousVertex, currentVertex }) => enterVertexCallbackCalls.push({ previousVertex, currentVertex });
        const leaveVertexCallback = ({ previousVertex, currentVertex }) => leaveVertexCallbackCalls.push({ previousVertex, currentVertex });

        ds.depthFirstSearch(graph, vertexA, {
            enterVertex: enterVertexCallback,
            leaveVertex: leaveVertexCallback,
            allowTraversal: ({ currentVertex, nextVertex }) =>
            {
                return !(currentVertex === vertexA && nextVertex === vertexB);
            },
        });

        assert.deepEqual(enterVertexCallbackCalls.length, 7);
        assert.deepEqual(leaveVertexCallbackCalls.length, 7);

        const enterVertexParamsMap = [
            { currentVertex: vertexA, previousVertex: null },
            { currentVertex: vertexD, previousVertex: vertexA },
            { currentVertex: vertexG, previousVertex: vertexD },
            { currentVertex: vertexE, previousVertex: vertexA },
            { currentVertex: vertexF, previousVertex: vertexE },
            { currentVertex: vertexD, previousVertex: vertexF },
            { currentVertex: vertexG, previousVertex: vertexD },
        ];

        for (let callIndex = 0; callIndex < graph.getAllVertices().length; callIndex += 1)
        {
            const params = enterVertexCallbackCalls[callIndex];
            assert.deepEqual(params.currentVertex, enterVertexParamsMap[callIndex].currentVertex);
            assert.deepEqual(params.previousVertex, enterVertexParamsMap[callIndex].previousVertex);
        }

        const leaveVertexParamsMap = [
            { currentVertex: vertexG, previousVertex: vertexD },
            { currentVertex: vertexD, previousVertex: vertexA },
            { currentVertex: vertexG, previousVertex: vertexD },
            { currentVertex: vertexD, previousVertex: vertexF },
            { currentVertex: vertexF, previousVertex: vertexE },
            { currentVertex: vertexE, previousVertex: vertexA },
            { currentVertex: vertexA, previousVertex: null },
        ];

        for (let callIndex = 0; callIndex < graph.getAllVertices().length; callIndex += 1)
        {
            const params = leaveVertexCallbackCalls[callIndex];
            assert.deepEqual(params.currentVertex, leaveVertexParamsMap[callIndex].currentVertex);
            assert.deepEqual(params.previousVertex, leaveVertexParamsMap[callIndex].previousVertex);
        }
    });
});
